//
// Created by 30986 on 2020/9/19.
//
#include <iostream>
using namespace std;
/* 宏定义 */
#define MAXSIZE 20						//一个用作示例的小顺序表的最大长度
#define LT(a,b) ((a)<(b))
/* 类型定义 */
typedef int KeyType;					//定义关键字类型为整数类型
typedef struct							//顺序表结构
{
    KeyType key;						//关键字项
    //使用结构体便于使用中扩展
}RcdType;								//记录类型
typedef struct
{
    RcdType r[MAXSIZE+1];				//r[0]闲置或用作哨兵单元
    int length;							//顺序表长度
}SqList_sort;							//顺序表类型


/* 类型定义 */
typedef SqList_sort HeapType;


/*
 * 已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义；
 * 调整H.r[s..m]成为一个大顶堆
 */
void HeapAdjust(HeapType &H,int s,int m)
{
    RcdType rc;
    rc = H.r[s];
    for (int j = 2*s; j < m; j*=2) {
        if (j<m && LT(H.r[j].key,H.r[j+1].key))   //LT(a<b)
            ++j;
        if (!LT(rc.key,H.r[j].key))break;
        H.r[s]=H.r[j];
        s=j;
    }
    H.r[s]=rc;
}
/*
 * 对顺序表H进行堆排序
 */
void HeapSort(HeapType &H)
{
    int i;
    RcdType tmp;
    for ( i=H.length/2;i>0;--i) //初始化堆,把H.r[1..H.length]建成大顶堆
        HeapAdjust(H,i,H.length);
    for ( i=H.length,i>1;i--)
    {
        tmp = H.r[1];
        H.r[1] = H.r[i];
        H.r[i] = tmp;

        HeapAdjust(H,1,i-1);
    }
}
